package j2025.j01;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @Author 猫大仙
 */
public class j0116 {
    /**
     * 279. 完全平方数
     * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
     *
     * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
     * @param n
     * @return
     */
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1]+1;
            for (int j = 2; j*j <=i ; j++) {
                dp[i] = Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }

    /**
     * 131. 分割回文串
     * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
     * 回文串
     *  。返回 s 所有可能的分割方案。
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        int len = s.length();
        List<List<String>> ret = new ArrayList<>();
        if (len == 0) {
            return ret;
        }
        Deque<String> path = new ArrayDeque<>();
        char[] str = s.toCharArray();
        dfs(str, 0, len, path, ret);
        return ret;
    }
    public void dfs(char[] str, int index, int len, Deque<String> path, List<List<String>> ret) {
        if(index == len){
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < len; i++) {
            if(!isPalindrome(str,index,i)){
                continue;
            }
            path.addLast(new String(str,index,i-index+1));
            dfs(str,i+1,len,path,ret);
            path.removeLast();
        }
    }
    public boolean isPalindrome(char[] s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
